import static jdk.nashorn.internal.objects.NativeMath.min;

public class Test34 {
    public static  boolean isufly(int num){
        while (num % 2 ==0) num = num /2;
        while (num % 5 ==0) num = num/5;
        while (num % 3 ==0) num = num/3;
        return  num == 1;
    }
    public static int getUglyNumber1(int index){
        if (index <= 0) return 0;
        int num = 0;
        int uglyindex = 0;
        while(uglyindex < index){
            num ++;
            if (isufly(num)) uglyindex++;
        }
        return num;
    }
    public static int getUglyNumber2(int index){
        if (index <= 0)
            return 0;
        int[] pUlyNumbers = new int[index];//丑数数组
        pUlyNumbers[0] = 1;//第一个丑数
        int nextUglyIndex = 1;//索引为1
        
        int p2 = 0;//能被2整除丑数索引
        int p3 = 0;
        int p5 = 0;
        
        while (nextUglyIndex < index){
            int min = min(pUlyNumbers[p2] * 2,pUlyNumbers[p3]*3,pUlyNumbers[p5]*5);//找到三个中最小的
            pUlyNumbers[nextUglyIndex] = min;//把下一个位置赋值为min
            while (pUlyNumbers[p2] * 2 <= pUlyNumbers[nextUglyIndex]) p2 ++;//如果当前的数小于目前位置的丑数。则索引++
            while (pUlyNumbers[p3] * 3 <= pUlyNumbers[nextUglyIndex]) p3 ++;
            while (pUlyNumbers[p5] * 5 <= pUlyNumbers[nextUglyIndex]) p5 ++;
            nextUglyIndex ++;
        }
        return pUlyNumbers[nextUglyIndex-1];
    }

    private static int min(int n1, int n2, int n3) {
        int min = n1 < n2 ? n1 : n2;
        return min < n3 ? min : n3;
    }

    public static void main(String[] args) {
        System.out.println(getUglyNumber1(1)); // 1
        System.out.println(getUglyNumber1(9)); // 10
        System.out.println(getUglyNumber1(10)); // 12
        System.out.println(getUglyNumber1(11)); // 15
        System.out.println(getUglyNumber1(1500)); // 859963392
        System.out.println(getUglyNumber2(0)); // 0
        System.out.println(getUglyNumber2(1)); // 1
        System.out.println(getUglyNumber2(9)); // 10
        System.out.println(getUglyNumber2(10)); // 12
        System.out.println(getUglyNumber2(11)); // 15
        System.out.println(getUglyNumber2(1500)); // 859963392
        System.out.println(getUglyNumber2(0)); // 0

    }
}
